package lhc.alg.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * description: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 *  106. 从中序与后序遍历序列构造二叉树
 *   递归 迭代想不明白
 * author: hongchen.liao
 * date:  2022/8/21
 */
public class _106_Construct_Binary_Tree_From_Inorder__And_Postorder_Traversal {


     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    class Solution {

        int post_idx;
        int[] postorder;
        int[] inorder;
        Map<Integer, Integer> idx_map = new HashMap<>();

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            this.postorder = postorder;
            this.inorder = inorder;
            //从后续遍历的最后一个元素开始
            this.post_idx = postorder.length-1;
            //建立位置与值 hash表
            int idx = 0;
            for(int val : inorder){
                idx_map.put(val, idx++);
            }
            return helper(0, inorder.length-1);
        }

        TreeNode helper(int in_left, int in_right){
            //如果这没有节点构造二叉树。就结束
            if(in_left > in_right){
                return null;
            }
            //选择post_idx的位置的元素作为这个节点根节点
            int root_val = postorder[post_idx];
            TreeNode root = new TreeNode(root_val);

            //根据root所在位置分成左右两颗子树
            int index = idx_map.get(root_val);

            post_idx--;
            //构造右子树
            root.right = helper(index+1, in_right);
            //构造左子树
            root.left = helper(in_left, index-1);
            return root;
        }

    }


}
